package org.example.myleet.p851;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Solution1 {
    /**
     * 官方解：拓扑排序方案
     * 拓扑排序的精髓是计算节点的入度，并从最小入度的节点开始遍历，遍历的节点移除，并移除对应关联节点的入度，然后继续访问0入度的节点，然后不断循环直至遍历所有节点
     * 拓扑排序的遍历使用类似BFS的方式，使用队列保存0入度的节点待访问
     */
    public int[] loudAndRich(int[][] richer, int[] quiet) {
        int n = quiet.length;
        int[] inDegree = new int[n];
        List<int[]>[] relationMap = new List[n];
        for (int[] relation : richer) {
            ++inDegree[relation[1]];
            if (null == relationMap[relation[0]]) {
                relationMap[relation[0]] = new ArrayList<>();
            }
            relationMap[relation[0]].add(relation);
        }
        Queue<Integer> queue = new LinkedList<>();
        int[] result = new int[n];
        for (int i = 0; i < n; ++i) {
            //初始化时需要给每个节点的结果初始化为自己
            result[i] = i;
            if (inDegree[i] == 0) {
                //所有0入度的节点入队
                queue.offer(i);
            }
        }
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; ++i) {
                //person是已经找到的最安静的人
                Integer person = queue.poll();
                List<int[]> relations = relationMap[person];
                if (null != relations && relations.size() > 0) {
                    for (int[] relation : relations) {
                        if (quiet[result[relation[1]]] > quiet[result[person]]) {
                            //找到更安静的人，更新关联节点的结果
                            result[relation[1]] = result[person];
                        }
                        if (--inDegree[relation[1]] == 0) {
                            //移除关联节点的入度，如果入度降为0，则节点入队
                            queue.offer(relation[1]);
                        }
                    }
                }
            }
        }
        return result;
    }
}
